package backtracking;

import java.util.*;


/**
 * 22.括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class generateParenthesis {
    List<String> res = new ArrayList<>();
    char[] arr = new char[]{'(', ')'};
    int[] map = new int[2];
    StringBuffer sb = new StringBuffer();

    public List<String> generateParenthesis(int n) {
        Arrays.fill(map, n);
        backtracking(n, 0);
        return res;
    }

    public void backtracking(int n, int start) {
        if (start == 2 * n && map[0] == 0 && map[1] == 0) {
            if (!istrue(sb.toString()))
                return;
            res.add(sb.toString());
            return;
        }
        if (map[0] < 0 || map[1] < 0)
            return;

        for (int i = 0; i < 2; i++) {
            sb.append(arr[i]);
            map[i]--;
            backtracking(n, start + 1);
            sb.deleteCharAt(sb.length() - 1);
            map[i]++;
        }
    }

    public boolean istrue(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }


}

/**
 * hot100二刷
 */
class Solution2 {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    /**
     * @param open  当前已使用的左括号数量
     * @param close 当前已使用的右括号数量
     */
    private void backtrack(List<String> res, StringBuilder sb, int open, int close, int n) {
        // 若左右括号都达到上限，则将拼接结果收集
        if (open == n && close == n) {
            res.add(sb.toString());
            return;
        }
        // 若左括号还没用完，继续选择左括号
        if (open < n) {
            sb.append('(');
            backtrack(res, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        // 若右括号数量少于左括号数量（保证有效性），继续选择右括号
        if (close < open) {
            sb.append(')');
            backtrack(res, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

}


